package com.example.linked.doublepointers;

import com.example.linked.ListNode;

public class Leetcode83_DeleteDuplicates {
    public static void main(String[] args) {
        // 1,1,2,2,3,3,4,5,6,6
        ListNode head = new ListNode(1);
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(2);
        ListNode node4 = new ListNode(3);
        ListNode node5 = new ListNode(3);
        ListNode node6 = new ListNode(4);
        ListNode node7 = new ListNode(5);
        ListNode node8 = new ListNode(6);
        ListNode node9 = new ListNode(6);
        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;
        node7.next = node8;
        node8.next = node9;

        ListNode res = new Solution().deleteDuplicates(head);
        ListNode cur = res;
        while (cur != null) {
            System.out.println(cur.val);
            cur = cur.next;
        }
    }

    static class Solution {

        /**
         * 解法二:双指针
         * 双指针直接定位相同元素段，然后将整个相同的元素段只保留第一个
         * p代表相同元素段的开头,q代表相同元素段的结尾
         * @param head
         * @return
         */
        public ListNode deleteDuplicates2(ListNode head) {
            if(head == null || head.next == null) {
                return head;
            }
            ListNode p, q;
            p = head;
            q = head.next;
            while (p != null && q != null) {
                if (p.val == q.val) {
                    while (q.next != null && q.val == q.next.val) { // q和q.next相同说明结尾指针还得后移
                        q = q.next;
                    }
                    // 退出内存循环说明q已经到了相同元素段的末尾，需要删除该段相同的元素
                    q = q.next;
                    p.next = q;
                } else {
                    p = p.next;
                    q = q.next;
                }
            }

            return head;
        }

        /**
         * 解法一:
         * 遍历链表，比较当前节点和下一个节点是否相等
         * 相等则删除后一个节点
         * @param head
         * @return
         */
        public ListNode deleteDuplicates1(ListNode head) {
            ListNode cur = head;
            while (cur != null && cur.next != null) {
                if (cur.val == cur.next.val) {
                    cur.next = cur.next.next;
                } else {
                    cur = cur.next;
                }
            }
            return head;
        }

        public ListNode deleteDuplicates(ListNode head) {
            return deleteDuplicates2(head);
        }
    }
}
